import java.util.HashSet;
import java.util.Set;

/**
 * 160. 相交链表
 */
public class Solution_160 {
    /**
     * 方法二：双指针
     * <p>
     * 时间复杂度：O(M+N)
     * <p>
     * 空间复杂度：O(1)
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = (A != null) ? A.next : headB;
            B = (B != null) ? B.next : headA;
        }
        return A;
    }

    /**
     * 方法一：哈希表
     * <p>
     * 时间复杂度：O(M+N)
     * <p>
     * 空间复杂度：O(max(M,N))
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();

        ListNode cur = headA;
        while (cur != null) {
            set.add(cur);
            cur = cur.next;
        }

        cur = headB;
        while (cur != null) {
            if (set.contains(cur)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    public static void main(String[] args) {
        Solution_160 solution = new Solution_160();
        // 链表公共部分
        ListNode common = new ListNode(8);
        common.next = new ListNode(4);
        common.next.next = new ListNode(5);
        // 链表A
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        headA.next.next = common;
        // 链表B
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(0);
        headB.next.next = new ListNode(1);
        headB.next.next.next = common;

        ListNode ans = solution.getIntersectionNode(headA, headB);
        System.out.println(ans.val);
    }
}
